Communication networks generally transport information in the form of packets, cells, or frames between nodes. Depending upon the particular protocol used to transport the information, a communication network may be categorized as a connection-oriented network or a connection-less network.
In a connection-oriented network, for example an Asynchronous Transfer Mode (ATM) network, the network establishes a connection for transporting cells between nodes, which may include, for example, switching systems and routers. When a node receives a cell, the node identifies a connection, for example a virtual circuit or a virtual path, associated with the cell in order to properly route the cell to the next node in the network. As a result, the node must retrieve from a memory the connection information associated with the cell within a fraction of the time for processing the cell. This task of retrieving the connection information impacts the performance of a node, especially as the address space of connection identifiers becomes large and unrestricted.
Although in a connection-less network, for example an Internet Protocol (IP) network, the network transports packets or frames without establishing connections between the nodes, the nodes identify forwarding information, for example output port addresses in the nodes, associated with packets for routing the packets to their destination nodes in the network. Like nodes in a connection-oriented network, a node in a connection-less network must retrieve the forwarding information associated with a packet within a fraction of the time for processing the packet. This task of retrieving the forwarding information impacts the performance of the node and the communications network as a whole.
Several solutions are known for storing and retrieving connection and forwarding information in connection-oriented and connection-less nodes. One solution uses a Content Addressable Memory (CAM) for storing and retrieving connection and forwarding information associated with cells and packets. CAM has a high incremental cost, however, and is not cost effective for processing large number of connections or network addresses.
Another solution uses a linear index into a Random Access Memory (RAM) for storing and retrieving information in a node. A linear index, however, requires a RAM address space that is as large as the address space for connection identifiers or addresses in a network, which can be large and unrestricted. Thus, the linear index is not a practical solution for ATM and IP networks.
Another known solution uses a hierarchical linear index into a RAM for storing and retrieving connection and forwarding information in a node. A hierarchical linear index uses a key into the RAM for retrieving the information. The key, however, must correspond to a predefined hierarchy, which puts a restriction on the allocation of connection identifiers or network addresses in the node. To maintain the hierarchy, the node must periodically restructure the hierarchy as the node inserts and deletes keys in the RAM. Restructuring the hierarchy generally requires significant resources and service interruptions unless the node reserves additional memory, which may be impractical and costly.
Yet another solution uses a binary search into a RAM for storing and retrieving connection and forwarding information in a node. The binary search uses a feedback from each search into the RAM before performing another search, and thus, significantly increases the retrieval times in the node.
Therefore, it is desirable to have a method and system for storing and retrieving connection and/or forwarding information in a communication node, and thus, to overcome the above-mentioned and other disadvantages of the prior art.